#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll inf=0x7fffffffffffff;
const int maxn=100000;

int n;
pair<int, int> a[maxn+1];
struct Node {
    int tag, f;
    pair<ll, int> i, a, ti, ta; //i:min a:max
    ll ans, ians, tans; //i:inv
} v[4*maxn+1];

void pushDown(int o, int l, int r) {
    v[o].f += v[o].tag;
    if (l!=r) v[o*2].tag+=v[o].tag, v[o*2+1].tag+=v[o].tag;
    v[o].tag = 0;
}

void pushUp(int o) {
    const Node &l=v[o*2], &r=v[o*2+1];
    Node &t=v[o];

    t.f = min(l.f, r.f);

    t.i = min(l.i, r.i);
    t.a = max(l.a, r.a);
    t.ans = max(max(l.ans, r.ans), r.a.first-l.i.first);
    t.ians = max(max(l.ians, r.ians), l.a.first-r.i.first);

    t.ti = l.f<=r.f ? l.ti : min(l.i, r.ti);
    t.ta = r.f<=l.f ? r.ta : max(r.a, l.ta);
    t.tans = max(max(l.f<=r.f ? l.tans : l.ians, r.f<=l.f ? r.tans : r.ians), l.f==r.f ? l.ta.first-r.ti.first : (l.f<r.f ? l.ta.first-r.i.first : l.a.first-r.ti.first));
}

void init(int o, int l, int r) {
    if (l==r) {
        v[o].tag=v[o].f=v[o].ans=v[o].ians=v[o].tans=0;
        v[o].i = v[o].a = {a[l].second, l};
        v[o].ti={inf, l}, v[o].ta={0, l};
    } else {
        int mid=(l+r)/2;
        init(o*2, l, mid);
        init(o*2+1, mid+1, r);
        pushUp(o);
    }
}

void add(int o, int l, int r, int tl, int tr, int tv) {
    pushDown(o, l, r);
    if (l==tl && r==tr) {
        v[o].tag+=tv;
        pushDown(o, l, r);
    } else {
        int mid=(l+r)/2;
        if (tl<=mid) add(o*2, l, mid, tl, min(tr, mid), tv);
        else pushDown(o*2, l, mid);
        if (tr>mid) add(o*2+1, mid+1, r, max(tl, mid+1), tr, tv);
        else pushDown(o*2, mid+1, r);
        pushUp(o);
    }
}

void dis(int o, int l, int r, int t) {
    pushDown(o, l, r);
    if (l==r) v[o].i.first=inf, v[o].a.first=0;
    else {
        int mid=(l+r)/2;
        if (t<=mid) dis(o*2, l, mid, t), pushDown(o*2+1, mid+1, r);
        else dis(o*2+1, mid+1, r, t), pushDown(o*2, l, mid);
        pushUp(o);
    }
}

pair<int, int> find(int o, int l, int r, int typ) {
    const Node &ls=v[o*2], &rs=v[o*2+1], &t=v[o];
    int mid=(l+r)/2;
    pushDown(o, l, r);
    pushDown(o*2, l, mid), pushDown(o*2+1, mid+1, r);
    if (typ==0) {
        if (rs.a.first-ls.i.first==t.ans) return {ls.i.second, rs.a.second};
        else if (ls.ans==t.ans) return find(o*2, l, mid, typ);
        else return find(o*2+1, mid+1, r, typ);
    } else if (typ==1) {
        if (ls.a.first-rs.i.first==t.ians) return {ls.a.second, rs.i.second};
        else if (ls.ians==t.ians) return find(o*2, l, mid, typ);
        else return find(o*2+1, mid+1, r, typ);
    } else {
        pair<ll, int> le, ri;
        if (ls.f<rs.f) le=ls.ta, ri=rs.i;
        else if (ls.f>rs.f) le=ls.a, ri=rs.ti;
        else le=ls.ta, ri=rs.ti;
        if (le.first-ri.first == t.tans) return {le.second, ri.second};
        else {
            if ((ls.f<=rs.f ? ls.tans : ls.ians) == t.tans) return find(o*2, l, mid, 1+(ls.f<=rs.f));
            else return find(o*2+1, mid+1, r, 1+(rs.f<=ls.f));
        }
    }
}

int main() {
    freopen("sky.in", "r", stdin);
    freopen("sky.out", "w", stdout);

    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d %d", &a[i].first, &a[i].second);
    }
    sort(a+1, a+n+1);

    ll ans=0;
    init(1, 1, n);
    for (int i=1; i<=n/2; i++) {
        int tv=0;
        pair<int, int> t={1, n}, x={1, n};
        if ((v[1].f && v[1].ans>=v[1].ians) || (!v[1].f && v[1].ans>=v[1].tans)) {
            if (v[1].ans) {
                ans += v[1].ans;
                t = x = find(1, 1, n, 0);
                x.first++, x.second--;
                tv = 1;
            }
        } else if (v[1].f) {
            if (v[1].ians) {
                ans += v[1].ians;
                t = x = find(1, 1, n, 1);
                tv = -1;
            }
        } else {
            if (v[1].tans) {
                ans += v[1].tans;
                t = x = find(1, 1, n, 2);
                tv = -1;
            }
        }
        add(1, 1, n, x.first, x.second, tv);
        dis(1, 1, n, t.first), dis(1, 1, n, t.second);

        printf("%lld\n", ans);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
